package algorithms.leaning.class18;

import common.util.MyUtil;

/**
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
 * 玩家A和玩家B依次拿走每张纸牌
 * 规定玩家A先拿，玩家B后拿
 * 但是每个玩家每次只能拿走最左或最右的纸牌
 * 玩家A和玩家B都绝顶聪明
 * 请返回最后获胜者的分数。
 *
 * @author guichang
 * @date 2021/6/17
 */

@SuppressWarnings("all")
public class Code2_动态规划_纸牌游戏最大分数 {

    public static void main(String[] args) {
        int[] cards = MyUtil.createArray(1, 100, 1, 1);
        MyUtil.print(maxScore(cards));
        MyUtil.print(maxScoreDp(cards));
    }

    public static int maxScore(int[] cards) {
        if (cards == null || cards.length == 0) {
            return 0;
        }
        int first = first(cards, 0, cards.length - 1);
        int second = second(cards, 0, cards.length - 1);
        return Math.max(first, second);
    }

    /**
     * L~R范围内先手姿态拿的最大分数
     */
    private static int first(int[] cards, int L, int R) {
        if (L == R) {
            return cards[L]; // 拿了就直接返回了
        }
        // 拿第一个
        int p1 = cards[L] + second(cards, L + 1, R);
        // 拿最后一个
        int p2 = cards[R] + second(cards, L, R - 1);
        // 取最大值
        return Math.max(p1, p2);
    }

    /**
     * L~R范围内后手姿态拿的最小分数
     */
    private static int second(int[] cards, int L, int R) {
        if (L == R) {
            return 0; // 没得拿了
        }
        // 拿第一个
        int p1 = first(cards, L + 1, R);
        // 拿最后一个
        int p2 = first(cards, L, R - 1);
        // 取最小值
        return Math.min(p1, p2);
    }

    /**
     * 严格位置依赖版本
     */
    public static int maxScoreDp(int[] cards) {
        if (cards == null || cards.length == 0) {
            return 0;
        }
        int N = cards.length;
        int[][] fdp = new int[N][N];
        int[][] sdp = new int[N][N];
        for (int i = 0; i < N; i++) {
            fdp[i][i] = cards[i];
            sdp[i][i] = 0; // 可忽略
        }
        // 整体从左往右
        for (int j = 1; j < N; j++) {
            // 内部右斜下
            int L = 0;
            int R = j;
            while (R < N) {
                fdp[L][R] = Math.max(cards[L] + sdp[L + 1][R], cards[R] + sdp[L][R - 1]);
                sdp[L][R] = Math.min(fdp[L + 1][R], fdp[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(fdp[0][N - 1], sdp[0][N - 1]);
    }


}